iT邦幫忙

2019 iT 邦幫忙鐵人賽

DAY 9
0

圖形的走訪 Traversal

指從某個頂點作為起點,依照某種順序,一個一個拜訪所有能到達的頂點。

走訪的順序分為: 廣度優先 (Breadth First Search)深度優先 (Depth First Search)

深度優先 (Depth First Search)

假定某一頂點為起始起點(X),接著任意選擇一個與起點相鄰的頂點(Y),再接著選擇與頂點(Y)相鄰的頂點,一直任意選擇相鄰的頂點,直到找到某一個頂點的相鄰頂點都被走訪過,就回到上一個走訪的頂點,再繼續選擇相鄰的頂點,直到所有頂點都被走訪完。

  • 頂點的選擇是使用後進先出(Last in First out,LIFO) 的方式管理,所以演算法可以使用 Stack 作為儲存的結構。

演算法 (迴圈版)

取得任一頂點作為起始頂點(X),將其Push至堆疊Stack中。
若Stack不為空,則重複迴圈
-> 從Stack中Pop出一個頂點(Y)
-> 走訪頂點(Y),並將所有與頂點(Y)相鄰且尚未被走訪過且不存在於Stack的頂點,Push至Stack
迴圈結束
  • 以下圖為例子
    https://ithelp.ithome.com.tw/upload/images/20181022/20112438feRq7IGozU.jpg

  • 走訪頂點的時機: 將頂點從堆疊中POP出

  • 其中一組拜訪順序為 A、D、F、I、G、H、E、C、B 的走訪步驟 :

步驟 說明 已走訪的頂點 Stack (頂端)(尾)
(0) 假設頂點A為起始點,Push(A) 無頂點 A
(1) Pop(A),走訪頂點A。將與A相鄰且未走訪的點Push到堆疊中,Push(B,C,D) A B、C、D
(2) Pop(D),走訪頂點D,將與D相鄰且未走訪的點Push到堆疊中,Push(E,F) A、D B、C、E、F
(3) Pop(F),走訪頂點F。將與F相鄰且未走訪的點Push到堆疊中,Push(G,I) A、D、F B、C、E、G、I
(4) Pop(I),走訪頂點I。與I相鄰的頂點F已被走訪過,故不進行Push A、D、F、I B、C、E、G
(5) Pop(G),走訪頂點G。將與G相鄰且未走訪的點Push到堆疊中,Push(H) A、D、F、I、G B、C、E、H
(6) Pop(H),走訪頂點H。與H相鄰的頂點G已被走訪過,而與H相鄰的頂點C已在堆疊中,故不進行Push A、D、F、I、G、H B、C、E
(7) Pop(E),走訪頂點E。與E相鄰的頂點D已被走訪過,故不進行Push A、D、F、I、G、H、E B、C
(8) Pop(C),走訪頂點C。與C相鄰的頂點A、H、G已被走訪過,故不進行Push A、D、F、I、G、H、E、C B
(9) Pop(B),走訪頂點B。與B相鄰的頂點A已被走訪過,故不進行Push A、D、F、I、G、H、E、C、B
(10) Stack為空,迴圈結束

參考

細談資料結構 第六版
ISBN 978-986-312-014-8


上一篇
[Data Structure][Graph] - Traversal - BFS
下一篇
[Data Structure][Graph] -Spanning Tree !
系列文
學習資料結構30天30
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

1 則留言

0
throughly410
iT邦新手 5 級 ‧ 2022-09-11 01:35:10

請問第二步為何不用push D節點?

嗨你好,是我遺漏了 D 節點 !
已經更新文章了呦 !
謝謝你認真閱讀 ~

/images/emoticon/emoticon37.gif

我要留言

立即登入留言